Packet classification and application of access control lists (ACLs) are employed by Internet routers to implement a number of advanced Internet services such as policy-based routing, rate-limiting, access control in firewalls, service differentiation, traffic shaping, traffic billing, etc. Each of these services requires the router to classify incoming packets into different classes and then to perform appropriate actions depending upon the packet's correspondence to one or more of the rules in the access control lists. For example, in packet routing applications, an incoming packet is classified to determine whether to forward or filter the packet, where to forward the packet to, what class of service the packet should receive, and/or how much should be charged for transmitting the packet. Sometimes a packet classifier embodies a set of policies or rules that define what actions are to be taken based upon the contents of one or more fields of the packet's header. The packet header, which typically includes source and destination addresses, source and destination port numbers, protocol information, and so on, may match more than one rule. For example, one rule in a firewall application can specify either a “permit” or “deny” action for a given set of source and destination addresses, another rule in the firewall application can specify either a “permit” or “deny” action for a given protocol, and yet another rule in the firewall application can specify either a “permit” or “deny” action for a particular source IP address and protocol.
Many packet classification systems employ content addressable memory (CAM) devices to store the rules of various ACLs. During packet classification look-up operations, selected information from an incoming packet's header is used to form a search key that is simultaneously compared with the rules stored in the CAM device, thereby allowing packet classification operations to be performed at very high speeds. However, although capable of very fast searching speeds, CAM devices are relatively large, expensive, and power-hungry. Thus, there is a need to reduce power consumption of CAM devices, for example, deployed in packet classification operations.
Like reference numerals refer to corresponding parts throughout the drawing figures.